1. Field of the Invention
The present invention relates to management of memory resources. More specifically, a method and apparatus for allocating shared memory resources and discarding incoming data as necessary.
2. Background
In a network environment, various traffic management techniques are used to control the flow of data throughout the network. Network devices often utilize buffers and queues to control the flow of network data. During periods of heavy network traffic or congestion, certain data cells or packets may be discarded to prevent buffer overflow or deadlock.
FIG. 1 illustrates a known switch 10 for use in a network environment. Switch 10 receives data cells from a plurality of input ports (labeled IN.sub.1 -IN.sub.M) and transmits data cells from a plurality of output ports (labeled OUT.sub.1 -OUT.sub.N). A plurality of input buffers 12 are coupled between the input ports and switch 10. A plurality of output buffers 14 are coupled between switch 10 and the output ports. As shown in FIG. 1, each input buffer 12 is separated from the remaining input buffers and dedicated to a particular port of switch 10. If a particular port is not active, then its associated input buffer cannot be used by another port. Instead, the buffer remains idle even if other buffers are fully utilized. For example, if the input buffer associated with input IN.sub.1 is full and the input buffer associated with IN.sub.2 is empty, incoming data on input IN.sub.1 will be discarded, and cannot be stored in the input buffer associated with IN.sub.2. Similarly, each output buffer 14 is separated from the remaining output buffers and dedicated to a particular output line.
To provide improved memory utilization, another type of network switch was developed having a shared memory buffer. An example of a shared memory switch is illustrated in FIG. 2. Shared memory switch 100 includes a plurality of inputs and a plurality of outputs. Rather than providing separate input buffers for each input, shared memory switch 100 includes a shared memory 102 which receives data cells or packets from any of the inputs.
When using a shared memory device, the memory resources must be allocated between the various ports coupled to the shared memory. Known switches utilize fixed discard thresholds for determining when to discard an incoming or outgoing data cell or packet. Thus, when the level of data associated with a particular port exceeds a fixed threshold value, the data cell or packet is discarded. Although a shared memory switch allows multiple ports to share a single memory buffer, the use of fixed thresholds for discarding data creates several problems.
If a single port is active, the port is limited by its fixed threshold. Thus, instead of utilizing the entire memory buffer, the memory usage by the single active port may not exceed the fixed threshold value. When the threshold value is reached, additional incoming cells must be discarded rather than being stored in the empty portions of the memory buffer. This results in an under-utilization of the memory buffer resources.
Another problem created by fixed thresholds results in an unequal allocation of memory resources among the various ports. To take advantage of the shared memory buffer, fixed thresholds are typically set higher than the "fair share" of the memory resources for each port. For example, if a shared memory device is accessed by four different ports, the "fair share" for each port is 25% of the available memory resources. However, if the threshold for each port is set at 25% of the total memory available, then the situation is similar to the prior art switch of FIG. 1 having separate memory buffers. In this situation, each switch may utilize a separate portion of the shared memory equal to its fair share. To provide better memory utilization, the fixed thresholds are typically set higher than the port's "fair share" of memory. Problems occur when all ports are active and certain ports use memory resources up to their threshold values. Since the fixed thresholds are set higher than the port's "fair share," overallocation of the memory resources may occur if several ports are active at the same time. This overallocation of memory resources may overload the buffer and cause the buffer to malfunction.
It is therefore desirable to provide a mechanism for managing a shared memory buffer in a manner that efficiently utilizes memory resources and prevents overload and unfair usage of memory resources.